//
//  ProblemOffer62.swift
//  TestProject
//
//  Created by 武侠 on 2022/3/4.
//  Copyright © 2022 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 62. 圆圈中最后剩下的数字
 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

 示例 1：
     输入: n = 5, m = 3
     输出: 3
 示例 2：
     输入: n = 10, m = 17
     输出: 2
 限制：
     1 <= n <= 10^5
     1 <= m <= 10^6
 */
class ProblemOffer62: NSObject {
    /*
     递归：
     假设长度为n-1的数，他最后的最后一个数是x：f(n-1) = x
     那么长度为n时，他的最后一个数就是：第一个计算m后 在加上f(n-1):
     f(n) = (m%n + x) %n = m%n + x%n = (m+x)%n = (m + f(n-1)) %n
     f(1) = 0
     */
    func lastRemaining(_ n: Int, _ m: Int) -> Int {
        return deep(n, m)
    }
    
    func deep(_ n: Int, _ m: Int) -> Int {
        if n <= 1 {
            return 0
        }
        let x = deep(n-1, m)
        return (m + x) % n
    }
}
